//
#include <iostream>
using namespace std;

void CountSort(int* arr, int size)
{
	int min, max;
	min = max = arr[0];
	for (int i = 1; i < size; i++)
	{
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
	}

	int range = max - min + 1;
	int* count = (int*)calloc ( range, sizeof(int) );
	if (!count)
	{
		perror("calloc fail!");
		exit(1);
	}

	for (int i = 0; i < size; i++)
	{
		count[arr[i]-min]++;
	}

	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[j++] = i + min;
		}
	}

	free(count);
}

void PrintArr(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;
}

int main()
{
	int arr[] = { 100, 109, 105, 102, 105, 107, 106 };
	int size = sizeof(arr) / sizeof(int);
	PrintArr(arr, size);

	CountSort(arr, size);
	
	PrintArr(arr, size);

	return 0;
}